package leetcode.linkedlist;

public interface OddEvenLinkedList328 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    class Solution {
        public ListNode oddEvenList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode oddHead = head;
            ListNode evenHead = head.next;
            ListNode oddP = oddHead;
            ListNode evenP = evenHead;
            while (evenP != null && evenP.next != null) {
                oddP.next = oddP.next.next;
                evenP.next = evenP.next.next;
                oddP = oddP.next;
                evenP = evenP.next;
            }
            oddP.next = evenHead;
            return oddHead;
        }
    }
}
